{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Missing Two LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: missingTwo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #消失的两个数字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？</p>\n",
    "\n",
    "<p>以任意顺序返回这两个数字均可。</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> <code>[1]</code>\n",
    "<strong>输出: </strong>[2,3]</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> <code>[2,3]</code>\n",
    "<strong>输出: </strong>[1,4]</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>nums.length &lt;=&nbsp;30000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [missing-two-lcci](https://leetcode.cn/problems/missing-two-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [missing-two-lcci](https://leetcode.cn/problems/missing-two-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = []"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "        twosum = sum(range(n+1)) - sum(nums)\n",
    "\n",
    "        if max(nums) < twosum//2:\n",
    "            x = max(nums) + 1\n",
    "            y = twosum - x\n",
    "            return(x, y)\n",
    "\n",
    "        x = 1\n",
    "        while x == sorted(nums)[x-1] and x <= twosum // 2:\n",
    "            x = x + 1\n",
    "        \n",
    "        y = twosum - x\n",
    "\n",
    "        return(x, y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\r\n",
    "        n = len(nums) + 2\r\n",
    "        z = n * (n + 1) // 2 - sum(nums)\r\n",
    "        n2 = z // 2\r\n",
    "        x = n2 * (n2 + 1) // 2\r\n",
    "        for num in nums:\r\n",
    "            if num <= n2:\r\n",
    "                x -= num\r\n",
    "        return [x, z - x]\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        should = 1\n",
    "        nums.sort()\n",
    "        for num in nums:\n",
    "            while num != should:\n",
    "                ans.append(should)\n",
    "                should += 1\n",
    "            should += 1\n",
    "        \n",
    "        cur = max(ans[-1] if ans else 0, nums[-1] if nums else 0)\n",
    "        while len(ans) < 2:\n",
    "            cur += 1\n",
    "            ans.append(cur)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "        \n",
    "        sum_num = (1+n) * n / 2\n",
    "        sum_now = sum(nums)\n",
    "        \n",
    "        sub_res_1 = sum_num - sum_now\n",
    "\n",
    "        sum_num_squre = 0\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            sum_num_squre += i ** 2\n",
    "        \n",
    "        sum_now_suqre = sum([nums[i] ** 2 for i in range(n-2)])\n",
    "        \n",
    "        sub_res_2 = sum_num_squre - sum_now_suqre\n",
    "        \n",
    "        for i in range(1, n+1):\n",
    "            x = i\n",
    "            y = sub_res_1 - x\n",
    "            \n",
    "            if x ** 2 + y ** 2 == sub_res_2:\n",
    "                return [int(x), int(y)]\n",
    "        return None\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "\n",
    "        que = 0\n",
    "        for num in nums:\n",
    "            que ^= num\n",
    "        full = 0\n",
    "        for i in range(1, n+1):\n",
    "            full ^= i\n",
    "\n",
    "        diff = full ^ que\n",
    "\n",
    "        lb = diff & (-diff)\n",
    "        \n",
    "        a = 0\n",
    "        for num in nums:\n",
    "            if num & lb:\n",
    "                a ^= num\n",
    "        for i in range(1, n+1) :\n",
    "            if i & lb:\n",
    "                a ^= i\n",
    "        \n",
    "        return [a, diff ^ a]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "        rest = (1 + n) * n // 2 - sum(nums)\n",
    "        mid = rest // 2\n",
    "        s = (1 + mid) * mid // 2\n",
    "        for x in nums:\n",
    "            if x <= mid:\n",
    "                s -= x\n",
    "        return [s, rest - s]\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        l, r= 1, len(nums) + 2\n",
    "        for i in range(len(nums)):\n",
    "            if l != nums[i]:\n",
    "                break\n",
    "            else:\n",
    "                l += 1\n",
    "        \n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            if r != nums[i]:\n",
    "                break\n",
    "            else:\n",
    "                r -= 1\n",
    "        return [l, r]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        nums += [0, 0]\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            while 0 <= nums[i]-1 < n and nums[nums[i]-1] != nums[i]:\n",
    "                nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]\n",
    "            # print(nums)\n",
    "\n",
    "        ret = []\n",
    "        for i in range(n):\n",
    "            if nums[i] != i+1:\n",
    "                ret.append(i+1)\n",
    "\n",
    "        # idx = n+1\n",
    "        # while len(ret) < 2:\n",
    "        #     ret.append(idx)\n",
    "        #     idx += 1\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        xorsum = 0\n",
    "        n = len(nums) + 2\n",
    "        for num in nums:\n",
    "            xorsum ^= num\n",
    "        for i in range(1, n + 1):\n",
    "            xorsum ^= i\n",
    "        \n",
    "        lsb = xorsum & (-xorsum)\n",
    "        type1 = type2 = 0\n",
    "        for num in nums:\n",
    "            if num & lsb:\n",
    "                type1 ^= num\n",
    "            else:\n",
    "                type2 ^= num\n",
    "        for i in range(1, n + 1):\n",
    "            if i & lsb:\n",
    "                type1 ^= i\n",
    "            else:\n",
    "                type2 ^= i\n",
    "        \n",
    "        return [type1, type2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        rel=[]\n",
    "        l=[0 for i in range(max(nums))]\n",
    "        for i in nums:\n",
    "            l[i-1]=1\n",
    "        # print(l)\n",
    "        for i,j in enumerate(l):\n",
    "            if j==0:\n",
    "                rel.append(i+1)\n",
    "        if len(rel)<2:\n",
    "            rel.append(i+2)\n",
    "        if len(rel)<2:\n",
    "            rel.append(i+3)\n",
    "        return rel\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        if nums==[]:\n",
    "            return [1,2]\n",
    "        nums.append(nums[0])\n",
    "        nums.append(nums[0])\n",
    "        for i in range(len(nums)):\n",
    "            nums[abs(nums[i])-1]=-abs(nums[abs(nums[i])-1])\n",
    "\n",
    "        return [i+1 for i in range(len(nums)) if nums[i]>0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        res = []\n",
    "        i = 0\n",
    "        while i < len(nums) or len(res) < 2:\n",
    "            i += 1\n",
    "            if i not in nums:\n",
    "                res.append(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        if nums==[]:\n",
    "            return [1,2]\n",
    "        nums.append(nums[0])\n",
    "        nums.append(nums[0])\n",
    "        for i in range(len(nums)):\n",
    "            nums[abs(nums[i])-1]=-abs(nums[abs(nums[i])-1])\n",
    "        ans=[]\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i]>0:\n",
    "                ans.append(i+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "        miss = []\n",
    "        for i in range(1,n+1):\n",
    "            if i not in nums:\n",
    "                miss.append(i)\n",
    "\n",
    "        return miss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[1]\n",
    "[2,3]\n",
    "\n",
    "nums.length <= 30000\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "        total_sum = n * (n + 1) // 2\n",
    "        total_xor = 0\n",
    "        actual_sum = 0\n",
    "        actual_xor = 0\n",
    "\n",
    "        # XOR all numbers from 1 to N and calculate the actual sum and XOR\n",
    "        for num in range(1, n + 1):\n",
    "            total_xor ^= num\n",
    "\n",
    "        for num in nums:\n",
    "            actual_sum += num\n",
    "            actual_xor ^= num\n",
    "\n",
    "        # The sum of the two missing numbers\n",
    "        sum_of_missing = total_sum - actual_sum\n",
    "        # The XOR of the two missing numbers\n",
    "        xor_of_missing = total_xor ^ actual_xor\n",
    "\n",
    "        # Get the rightmost bit where the two missing numbers differ\n",
    "        rightmost_different_bit = xor_of_missing & -xor_of_missing\n",
    "\n",
    "        # Initialize the missing numbers to zero\n",
    "        missing1 = missing2 = 0\n",
    "\n",
    "        # Partition the numbers and XOR\n",
    "        for num in range(1, n + 1):\n",
    "            if num & rightmost_different_bit:\n",
    "                missing1 ^= num\n",
    "            else:\n",
    "                missing2 ^= num\n",
    "\n",
    "        for num in nums:\n",
    "            if num & rightmost_different_bit:\n",
    "                missing1 ^= num\n",
    "            else:\n",
    "                missing2 ^= num\n",
    "\n",
    "        # missing1 and missing2 are the missing numbers\n",
    "        return [missing1, missing2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "        two_xor_sum = 0\n",
    "        for num in nums:\n",
    "            two_xor_sum ^= num\n",
    "        for i in range(1, n + 1):\n",
    "            two_xor_sum ^= i\n",
    "\n",
    "        lowbit = two_xor_sum & (-two_xor_sum)\n",
    "        group_a, group_b = 0, 0\n",
    "\n",
    "        for num in nums:\n",
    "            if num & lowbit:\n",
    "                group_a ^= num\n",
    "            else:\n",
    "                group_b ^= num\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            if i & lowbit:\n",
    "                group_a ^= i\n",
    "            else:\n",
    "                group_b ^= i\n",
    "        \n",
    "        return [group_a, group_b]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums):\n",
    "        n = len(nums) + 2\n",
    "        total = n * (n + 1) // 2\n",
    "        sum_nums = sum(nums)\n",
    "        pivot = (total - sum_nums) // 2\n",
    "\n",
    "        total_left_xor = 0\n",
    "        total_right_xor = 0\n",
    "        nums_left_xor = 0\n",
    "        nums_right_xor = 0\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            if i <= pivot:\n",
    "                total_left_xor ^= i\n",
    "            else:\n",
    "                total_right_xor ^= i\n",
    "\n",
    "        for num in nums:\n",
    "            if num <= pivot:\n",
    "                nums_left_xor ^= num\n",
    "            else:\n",
    "                nums_right_xor ^= num\n",
    "\n",
    "        return [total_left_xor ^ nums_left_xor, total_right_xor ^ nums_right_xor]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        ret=0\n",
    "        for num in nums:\n",
    "            ret^=num\n",
    "        for i in range(1,len(nums)+3):\n",
    "            ret^=i\n",
    "        lsb=ret&(-ret)\n",
    "        a=b=0\n",
    "        for num in nums:\n",
    "            if num&lsb:\n",
    "                a^=num\n",
    "            else: b^=num\n",
    "        for i in range(1,len(nums)+3):\n",
    "            if(lsb&i):\n",
    "                a^=i\n",
    "            else: b^=i\n",
    "        return [a,b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "        z = n * (n + 1) // 2 - sum(nums)\n",
    "        n2 = z // 2\n",
    "        x = n2 * (n2 + 1) // 2\n",
    "        for num in nums:\n",
    "            if num <= n2:\n",
    "                x -= num\n",
    "        return [x, z - x]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[1]\n",
    "[2,3]\n",
    "\n",
    "nums.length <= 30000\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "        total_sum = n * (n + 1) // 2\n",
    "        total_xor = 0\n",
    "        actual_sum = 0\n",
    "        actual_xor = 0\n",
    "\n",
    "        # XOR all numbers from 1 to N and calculate the actual sum and XOR\n",
    "        for num in range(1, n + 1):\n",
    "            total_xor ^= num\n",
    "\n",
    "        for num in nums:\n",
    "            actual_sum += num\n",
    "            actual_xor ^= num\n",
    "\n",
    "        # The sum of the two missing numbers\n",
    "        sum_of_missing = total_sum - actual_sum\n",
    "        # The XOR of the two missing numbers\n",
    "        xor_of_missing = total_xor ^ actual_xor\n",
    "\n",
    "        # Get the rightmost bit where the two missing numbers differ\n",
    "        rightmost_different_bit = xor_of_missing & -xor_of_missing\n",
    "\n",
    "        # Initialize the missing numbers to zero\n",
    "        missing1 = missing2 = 0\n",
    "\n",
    "        # Partition the numbers and XOR\n",
    "        for num in range(1, n + 1):\n",
    "            if num & rightmost_different_bit:\n",
    "                missing1 ^= num\n",
    "            else:\n",
    "                missing2 ^= num\n",
    "\n",
    "        for num in nums:\n",
    "            if num & rightmost_different_bit:\n",
    "                missing1 ^= num\n",
    "            else:\n",
    "                missing2 ^= num\n",
    "\n",
    "        # missing1 and missing2 are the missing numbers\n",
    "        return [missing1, missing2]\n",
    "    \"\"\"\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)+2\n",
    "        totalXor = 0; actualXor = 0\n",
    "        for num in range(1, n+1):\n",
    "            totalXor ^= num\n",
    "        for num in nums:\n",
    "            actualXor ^= num\n",
    "        xorOfMissing = totalXor ^ actualXor\n",
    "        rightmostDifferentBit = xorOfMissing & -xorOfMissing\n",
    "\n",
    "        missing1, missing2 = 0, 0\n",
    "        for num in range(1, n + 1):\n",
    "            if num & rightmostDifferentBit:\n",
    "                missing1 ^= num\n",
    "            else:\n",
    "                missing2 ^= num\n",
    "\n",
    "        for num in nums:\n",
    "            if num & rightmostDifferentBit:\n",
    "                missing1 ^= num\n",
    "            else:\n",
    "                missing2 ^= num\n",
    "\n",
    "        return [missing1, missing2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        将i放置到nums[i-1]的位置\n",
    "        具体而言 这个放置不是真的放置 只需要把nums[i-1]中的元素设置为负数即可\n",
    "        且由于nums长度是N-2 所以N和N-1就用两个变量来记录\n",
    "        随后遍历 看nums中哪个下标对应的元素还是正数 那么这个下标+1就是缺失的值\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        maxFlag,secondMaxFlag = False,False #最大和次大是否存在的标志\n",
    "        for i in range(n):\n",
    "            if abs(nums[i])<= n:\n",
    "                nums[abs(nums[i])-1] = -nums[abs(nums[i])-1]\n",
    "            elif abs(nums[i])== n+1:\n",
    "                secondMaxFlag = True\n",
    "            else:\n",
    "                maxFlag = True\n",
    "        rs = []\n",
    "        for i in range(n):\n",
    "            if nums[i]>0:\n",
    "                rs.append(i+1)\n",
    "        if not maxFlag:\n",
    "            rs.append(n+2)\n",
    "        if not secondMaxFlag:\n",
    "            rs.append(n+1)\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        diff = 1\n",
    "        res = []\n",
    "        i = 0\n",
    "        while i < len(nums):\n",
    "            while i + diff != nums[i]:\n",
    "                res.append(i + diff)\n",
    "                diff += 1\n",
    "            i += 1\n",
    "            if len(res) == 2:\n",
    "                break\n",
    "        \n",
    "        while len(res) < 2:\n",
    "            res.append(i+diff)\n",
    "            i += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        # 利用 Single Number III\n",
    "        n = len(nums)\n",
    "        x_xor_y = 0  # assume x and y are two missing elements and only appears once after XOR with [1..n+2]\n",
    "        for num in nums:\n",
    "            x_xor_y ^= num    \n",
    "\n",
    "        for d in range(1, n + 3):\n",
    "            x_xor_y ^= d \n",
    "\n",
    "        # 两个只出现一次的数x, y必然不相等，则x, y的二进制至少有一位不同，据此可将nums分成包含x和y的两个子数组。\n",
    "        last1Bit = x_xor_y & ~(x_xor_y - 1)\n",
    "        # 易知这两子数组都满足：除一个数字之外，其他数字都出现了两次。分别对两子数组遍历执行异或操作，即可得到两个只出现一次的数字x, y\n",
    "        x, y = 0, 0\n",
    "        for num in nums:\n",
    "            if num & last1Bit == 0: \n",
    "                x ^= num\n",
    "            else:\n",
    "                y ^= num  \n",
    "\n",
    "        for d in range(1, n + 3):\n",
    "            if d & last1Bit == 0:\n",
    "                x ^= d\n",
    "            else:\n",
    "                y ^= d \n",
    "\n",
    "        return [x, y] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        nums = [0] + nums + [0, 0]\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            j = i\n",
    "            while nums[j] != 0 and nums[j] != j:\n",
    "                k = nums[j]\n",
    "                nums[j], nums[k] = nums[k], nums[j]\n",
    "        ans = []\n",
    "        for i, x in enumerate(nums):\n",
    "            if i and x == 0:\n",
    "                ans.append(i)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "        nums.extend([n+1] * 2)\n",
    "        for i in range(n-2):\n",
    "            nums[abs(nums[i])-1] *= -1\n",
    "        return [i+1 for i in range(n) if nums[i] > 0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "\n",
    "        n = len(nums)\n",
    "        tmp = nums + [n+2,n+2]\n",
    "        for i in range(n+2):\n",
    "            p = abs(tmp[i])-1\n",
    "            tmp[p] = -tmp[p]\n",
    "        ans = []\n",
    "        for i in range(n+2):\n",
    "            if tmp[i] > 0:\n",
    "                ans.append(i+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        \"\"\"\n",
    "        异或 将1-N和nums中所有元素异或得到x\n",
    "        显然x=x1^x2 其中x1和x2就是缺失的两个数字\n",
    "        取出x二进制中最低位为1的那位（通过x&-x操作），设它在第l位\n",
    "        那么x1和x2的第l位一个为1 一个为0 这样x的第l位才是1\n",
    "        这样可以把1-n和nums中的元素分为两个类别，一类第l位为0，另一类第l位是1\n",
    "        这样可以发现，如果已经在nums中出现一次，那么两次出现都会在一类，而x1和x2只会出现一次\n",
    "        这样将每个类里的元素异或起来就得到了x1和x2\n",
    "        \"\"\"\n",
    "        n = len(nums)+2\n",
    "        x = 0\n",
    "        for num in nums:\n",
    "            x ^= num\n",
    "        for i in range(1,n+1):\n",
    "            x ^= i\n",
    "        l = x&(-x) #x的第一个1出现在第l位\n",
    "        x1,x2 = 0,0\n",
    "        for num in nums:\n",
    "            if num&l:\n",
    "                x1 ^= num\n",
    "            else:\n",
    "                x2 ^= num    \n",
    "        for i in range(1,n+1):\n",
    "            if i&l:\n",
    "                x1 ^= i\n",
    "            else:\n",
    "                x2 ^= i\n",
    "        return [x1,x2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "\n",
    "        # 计算缺失两个数字的总和和平方和\n",
    "        total_missing = n * (n + 1) // 2\n",
    "        square_total_missing = n * (n + 1) * (2 * n + 1) // 6\n",
    "\n",
    "        # 计算实际数组的总和和平方和\n",
    "        total_actual = sum(nums)\n",
    "        square_total_actual = sum(x ** 2 for x in nums)\n",
    "\n",
    "        # 计算缺失的数字\n",
    "        missing_sum = total_missing - total_actual\n",
    "        missing_square_sum = square_total_missing - square_total_actual\n",
    "\n",
    "        # 计算缺失的两个数字\n",
    "        # 设缺失的两个数字为a和b，那么a + b = missing_sum，a^2 + b^2 = missing_square_sum\n",
    "        # 解这个二元一次方程组\n",
    "        # 得到 a = (missing_sum + sqrt(2 * missing_square_sum - missing_sum^2)) / 2\n",
    "        # b = missing_sum - a\n",
    "        a = (missing_sum + ((2 * missing_square_sum - missing_sum ** 2) ** 0.5)) / 2\n",
    "        b = missing_sum - a\n",
    "\n",
    "        return [int(a), int(b)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        x = 0\n",
    "        n = len(nums)\n",
    "        \n",
    "        for a in nums:\n",
    "            x ^= a\n",
    "\n",
    "        for b in range(1, n+2+1):\n",
    "            x ^= b        \n",
    "        \n",
    "        lb = x & (-x)\n",
    "        \n",
    "        y = 0\n",
    "        for a in nums:\n",
    "            if a & lb:\n",
    "                y ^= a\n",
    "        \n",
    "        for b in range(1, n+2+1):\n",
    "            if b & lb:\n",
    "                y ^= b\n",
    "            \n",
    "        return [y, y^x]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        #sort排序时间复杂度O(nlogn)，不符合O(n)要求\n",
    "        # nums.sort()\n",
    "        # res,flag,n,i,j = [],0,len(nums),0,0\n",
    "        # while i<n:\n",
    "        #     if nums[i]==j+1:\n",
    "        #         i+=1\n",
    "        #         j+=1\n",
    "        #         continue\n",
    "        #     res.append(j+1)\n",
    "        #     if len(res)==2:\n",
    "        #         return res\n",
    "        #     j+=1\n",
    "        # k = 0\n",
    "        # while len(res)<2:\n",
    "        #     res.append(n+2-k)\n",
    "        #     k+=1\n",
    "        # return res\n",
    "        n,acc = len(nums),0\n",
    "        for i in range(1,n+3):\n",
    "            acc^=i\n",
    "        for c in nums:\n",
    "            acc^=c\n",
    "        flag = acc&(-acc)\n",
    "        re1,re2 = 0,0\n",
    "        for c in nums:\n",
    "            if c&flag:\n",
    "                re1^=c\n",
    "            else:\n",
    "                re2^=c\n",
    "        for i in range(1,n+3):\n",
    "            if i&flag:\n",
    "                re1^=i\n",
    "            else:\n",
    "                re2^=i\n",
    "        return [re1,re2]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "        sum_ = (1 + n) * n // 2 - sum(nums)\n",
    "\n",
    "        t = sum_ // 2\n",
    "\n",
    "        res = (1 + t) * t // 2\n",
    "\n",
    "        for n in nums:\n",
    "            if n <= t:\n",
    "                res -= n\n",
    "        \n",
    "        return [res, sum_ - res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        xors = 0\n",
    "        for num in nums:\n",
    "            xors ^= num\n",
    "        for i in range(n+2):\n",
    "            xors ^= (i+1)\n",
    "\n",
    "        flag = xors & -xors\n",
    "        t1 = t2 = 0\n",
    "        for num in nums:\n",
    "            if num & flag:\n",
    "                t1 ^= num\n",
    "            else:\n",
    "                t2 ^= num\n",
    "        \n",
    "        for i in range(n+2):\n",
    "            if (i+1) & flag:\n",
    "                t1 ^= (i+1)\n",
    "            else:\n",
    "                t2 ^= (i+1)\n",
    "        \n",
    "        return [t1, t2]\n",
    "\n",
    "\n",
    "        # nums += [0, 0]\n",
    "        # n = len(nums)\n",
    "        # for i in range(n):\n",
    "        #     while 0 <= nums[i]-1 < n and nums[nums[i]-1] != nums[i]:\n",
    "        #         nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]\n",
    "        #     # print(nums)\n",
    "\n",
    "        # ret = []\n",
    "        # for i in range(n):\n",
    "        #     if nums[i] != i+1:\n",
    "        #         ret.append(i+1)\n",
    "\n",
    "        # # idx = n+1\n",
    "        # # while len(ret) < 2:\n",
    "        # #     ret.append(idx)\n",
    "        # #     idx += 1\n",
    "\n",
    "        # return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        xor = 0 \n",
    "        for n in nums:\n",
    "            xor = xor ^ n \n",
    "        \n",
    "        for n in range(0, len(nums)+2):\n",
    "            xor = xor ^ (n+1)\n",
    "        \n",
    "        lowbit = xor & (-xor)  # 缺失的两个数的最低位 1\n",
    "        a = 0 \n",
    "        for n in nums:  # 遍历一遍 nums\n",
    "            if n & lowbit:  # 先考虑最低位 1 为 lowbit 的那个缺失的数\n",
    "                a = a ^ n  # \n",
    "        \n",
    "        for n in range(0, len(nums)+2):  \n",
    "            # 遍历一遍完整的 1到 len(nums)+2, 缺失的一个数会只出现1次，其他数都会出现\n",
    "            # 两次，异或自身为 0，所以最终会得到缺失的最低位为 lowbit 的那个数\n",
    "            if (n+1) & lowbit:\n",
    "                a = a ^ (n+1) \n",
    "        b = a ^ xor  # xor=a^b, a^xor = a^b^a = b 得到另一个数\n",
    "        return [a, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "        s1, s2 = 0, 0\n",
    "        t1, t2 = 0, 0\n",
    "        for i in range(1, n + 1):\n",
    "            if i - 1 < len(nums):\n",
    "                s1 += nums[i - 1]\n",
    "                s2 += nums[i - 1] * nums[i - 1]\n",
    "            t1 += i\n",
    "            t2 += i * i\n",
    "        p, q = t1 - s1, t2 - s2\n",
    "        delta = int(math.sqrt(2 * q - p * p))\n",
    "        return [(p - delta) // 2, (p + delta) // 2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        sum_nums=sum(nums)\n",
    "        n=len(nums)\n",
    "        a_plus_b=(3+n)*(n+2)//2-sum_nums\n",
    "        \n",
    "        half_a_plus_b=a_plus_b//2\n",
    "        sum_half_a_plus_b=(half_a_plus_b+1)*half_a_plus_b//2\n",
    "        half_ab_nums=0\n",
    "        for x in nums:\n",
    "            if x <=half_a_plus_b:\n",
    "                half_ab_nums+=x\n",
    "        a=sum_half_a_plus_b-half_ab_nums\n",
    "        b=a_plus_b-a \n",
    "        return [a,b]\n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        xor = 0 \n",
    "        for n in nums:\n",
    "            xor = xor ^ n \n",
    "        \n",
    "        for n in range(0, len(nums)+2):\n",
    "            xor = xor ^ (n+1)\n",
    "        \n",
    "        lowbit = xor & (-xor) \n",
    "        a = 0 \n",
    "        for n in nums:\n",
    "            if n & lowbit:\n",
    "                a = a ^ n  \n",
    "        \n",
    "        for n in range(0, len(nums)+2):\n",
    "            if (n+1) & lowbit:\n",
    "                a = a ^ (n+1) \n",
    "        b = a ^ xor \n",
    "        return [a, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "        xor = 0\n",
    "        for i in range(1,n+1):\n",
    "            xor ^= i\n",
    "        \n",
    "        for num in nums:\n",
    "            xor ^= num\n",
    "        \n",
    "        mask = 1\n",
    "        while xor & mask == 0:\n",
    "            mask <<= 1\n",
    "        \n",
    "        xor1 = 0\n",
    "        xor2 = 0\n",
    "        for i in range(1,n+1):\n",
    "            if i & mask:\n",
    "                xor1 ^= i\n",
    "            else:\n",
    "                xor2 ^= i\n",
    "            \n",
    "        for num in nums:\n",
    "            if num & mask:\n",
    "                xor1 ^= num\n",
    "            else:\n",
    "                xor2 ^= num\n",
    "        \n",
    "        return [xor1, xor2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        N = len(nums) + 2\n",
    "        res = []\n",
    "        expect_sum = (1 + N) * N // 2\n",
    "        current_sum = sum(nums)\n",
    "        diff = expect_sum - current_sum\n",
    "\n",
    "        if diff % 2 == 0:\n",
    "            num_pos = diff // 2 - 1\n",
    "            two_sum = (1 + num_pos) * num_pos // 2\n",
    "        else:\n",
    "            num_pos = diff // 2\n",
    "        two_sum = (1 + num_pos) * num_pos // 2\n",
    "        \n",
    "        for n in nums:\n",
    "            if n <= num_pos:\n",
    "                two_sum -= n\n",
    "            \n",
    "        return [two_sum, diff - two_sum]\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        a,b=0,0\n",
    "        aa,bb = True,True\n",
    "        for i in range(len(nums)):\n",
    "            if bb == False:\n",
    "                break\n",
    "            if aa == True:\n",
    "                if nums[i] != i + 1:\n",
    "                    a = i + 1\n",
    "                    aa = False\n",
    "            elif bb == True:\n",
    "                if nums[i - 1] != i + 1:\n",
    "                    b = i + 1\n",
    "                    bb = False\n",
    "        \n",
    "        if a == 0:\n",
    "            return [nums[-1]+1,nums[-1] + 2]\n",
    "        elif b == 0:\n",
    "            if nums[-1] - len(nums) == 1:\n",
    "                return [a,nums[-1]+1]\n",
    "            else:\n",
    "                return [a,nums[-1] -1] \n",
    "        else:\n",
    "            return [a,b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "        xor = 0\n",
    "        for i in nums:\n",
    "            xor ^= i\n",
    "        for j in range(1, n + 1):\n",
    "            xor ^= j\n",
    "        \n",
    "        diff = xor & (-xor)\n",
    "        a = 0\n",
    "        for i in nums:\n",
    "            if i & diff:\n",
    "                a ^= i\n",
    "        for j in range(1, n + 1):\n",
    "            if j & diff:\n",
    "                a ^= j\n",
    "        b = xor ^ a\n",
    "\n",
    "        return [a, b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n=len(nums)+2\n",
    "        xor=0\n",
    "        for v in nums:\n",
    "            xor^=v\n",
    "        for i in range(1,n+1):\n",
    "            xor^=i\n",
    "        diff=xor&(-xor)\n",
    "        a=0\n",
    "        for v in nums:\n",
    "            if v&diff:\n",
    "                a^=v\n",
    "        for i in range(1,n+1):\n",
    "            if i&diff:\n",
    "                a^=i\n",
    "        b=xor^a\n",
    "        return [a,b]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        #sort排序时间复杂度O(nlogn)，不符合O(n)要求\n",
    "        # nums.sort()\n",
    "        # res,flag,n,i,j = [],0,len(nums),0,0\n",
    "        # while i<n:\n",
    "        #     if nums[i]==j+1:\n",
    "        #         i+=1\n",
    "        #         j+=1\n",
    "        #         continue\n",
    "        #     res.append(j+1)\n",
    "        #     if len(res)==2:\n",
    "        #         return res\n",
    "        #     j+=1\n",
    "        # k = 0\n",
    "        # while len(res)<2:\n",
    "        #     res.append(n+2-k)\n",
    "        #     k+=1\n",
    "        # return res\n",
    "        n,acc = len(nums),0\n",
    "        for i in range(1,n+3):\n",
    "            acc^=i\n",
    "        for c in nums:\n",
    "            acc^=c\n",
    "        flag = acc&(-acc)\n",
    "        re1,re2 = 0,0\n",
    "        for c in nums:\n",
    "            if c&flag:\n",
    "                re1^=c\n",
    "            else:\n",
    "                re2^=c\n",
    "        for i in range(1,n+3):\n",
    "            if i&flag:\n",
    "                re1^=i\n",
    "            else:\n",
    "                re2^=i\n",
    "        return [re1,re2]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        nums.sort()\n",
    "        res,flag,n,i,j = [],0,len(nums),0,0\n",
    "        while i<n:\n",
    "            if nums[i]==j+1:\n",
    "                i+=1\n",
    "                j+=1\n",
    "                continue\n",
    "            res.append(j+1)\n",
    "            if len(res)==2:\n",
    "                return res\n",
    "            j+=1\n",
    "        k = 0\n",
    "        # print(res)\n",
    "        while len(res)<2:\n",
    "            res.append(n+2-k)\n",
    "            k+=1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "        xor = lambda x,y:x^y\n",
    "\n",
    "        val = reduce(xor, nums) ^ reduce(xor, list(range(1, n + 1)))\n",
    "\n",
    "        lowbit = val & ( -val)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for nn in nums:\n",
    "            if nn & lowbit:\n",
    "                res ^= nn\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            if i & lowbit:\n",
    "                res ^= i\n",
    "\n",
    "        return [res, val ^ res]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "[1]\n",
    "[2,3]\n",
    "\n",
    "nums.length <= 30000\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)+2\n",
    "        xor = 0\n",
    "        for x in nums:\n",
    "            xor ^= x\n",
    "        for x in range(1, n+1):\n",
    "            xor ^= x\n",
    "        rightBit = xor & -xor\n",
    "        missing1, missing2 = 0, 0\n",
    "        for x in range(1, n+1):\n",
    "            if x & rightBit:\n",
    "                missing1 ^= x\n",
    "            else:\n",
    "                missing2 ^= x\n",
    "        for x in nums:\n",
    "            if x & rightBit:\n",
    "                missing1 ^= x\n",
    "            else:\n",
    "                missing2 ^= x\n",
    "        return [missing1, missing2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        xorsum = 0\n",
    "        n = len(nums) + 2  # 因为缺了两个数字，所以总长度应该是 len(nums) + 2\n",
    "        for num in nums:\n",
    "            xorsum ^= num  # 计算数组中所有数字的 XOR\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            xorsum ^= i  # 计算从1到N所有数字的 XOR\n",
    "\n",
    "        # 找出 xorsum 中最低设置位\n",
    "        lsb = xorsum & (-xorsum)\n",
    "        \n",
    "        type1 = 0\n",
    "        type2 = 0\n",
    "        for num in nums:\n",
    "            if num & lsb:  # 判断 num 在哪一组\n",
    "                type1 ^= num  # 计算第一组的 XOR\n",
    "            else:\n",
    "                type2 ^= num  # 计算第二组的 XOR\n",
    "        \n",
    "        for i in range(1, n + 1):\n",
    "            if i & lsb:  # 判断 i 在哪一组\n",
    "                type1 ^= i  # 计算第一组的 XOR\n",
    "            else:\n",
    "                type2 ^= i  # 计算第二组的 XOR\n",
    "        \n",
    "        return [type1, type2]  # 返回两个缺失的数字\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "        cur = n * (1 + n) // 2 - sum(nums)\n",
    "        tot, t = cur, cur // 2\n",
    "        cur = t * (1 + t) // 2 - sum([x for x in nums if x <= t])\n",
    "        return [cur, tot - cur]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        \n",
    "        # 先找缺失值的和\n",
    "        n = len(nums)\n",
    "        \n",
    "        m = n+2\n",
    "        su = ((1+m)*m)//2-sum(nums)\n",
    "        \n",
    "        t = su//2\n",
    "\n",
    "        temp = sum([x for x in nums if x<=t])\n",
    "        \n",
    "        res1 = ((1+t)*t)//2 - temp\n",
    "        return [res1,su-res1]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        N = len(nums) + 2\n",
    "        should = N * (N + 1) // 2\n",
    "        real = sum(nums)\n",
    "        two_sum = should - real\n",
    "        half = two_sum // 2\n",
    "        first = (1 + half) * half // 2 - sum([x for x in nums if x <= half])\n",
    "        return [first, two_sum - first]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        length = len(nums)\n",
    "        N = length + 2\n",
    "        sum = 0\n",
    "        for i in nums:\n",
    "            sum ^= i\n",
    "        for i in range(1, N+1):\n",
    "            sum ^= i\n",
    "        \n",
    "        tmp_sum = sum\n",
    "        sum &= -sum\n",
    "        sum1 = 0\n",
    "        for i in nums:\n",
    "            if i & sum != 0:\n",
    "                sum1 ^= i\n",
    "        for i in range(1, N+1):\n",
    "            if i & sum != 0:\n",
    "                sum1 ^= i\n",
    "        sum2 = tmp_sum ^ sum1\n",
    "        return [sum1, sum2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "        xor_sum = 0\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            xor_sum ^= i\n",
    "        for num in nums:\n",
    "            xor_sum ^= num\n",
    "        \n",
    "        lsb = xor_sum & (-xor_sum)\n",
    "\n",
    "        xor_sum_1, xor_sum_2 = 0, 0\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            if i & lsb:\n",
    "                xor_sum_1 ^= i\n",
    "            else:\n",
    "                xor_sum_2 ^= i\n",
    "        \n",
    "        for num in nums:\n",
    "            if num & lsb:\n",
    "                xor_sum_1 ^= num\n",
    "            else:\n",
    "                xor_sum_2 ^= num\n",
    "\n",
    "        return xor_sum_1, xor_sum_2\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums) + 2\n",
    "        cur = n * (n+1) // 2 - sum(nums)\n",
    "        mid = cur // 2\n",
    "        pre = mid * (mid+1) // 2 - sum([k for k in nums if k <= mid])\n",
    "        return [pre, cur - pre]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        num = 0\n",
    "        for i in nums:\n",
    "            cur_num = 1<<(i-1)\n",
    "            num = num^cur_num\n",
    "        \n",
    "        res = []\n",
    "        index = 1\n",
    "        while len(res)<2:\n",
    "            if num % 2 == 0:\n",
    "                res.append(index)\n",
    "            num = num>>1\n",
    "            index += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        xorsum = 0\n",
    "        n = len(nums) + 2\n",
    "        for num in nums:\n",
    "            xorsum ^= num\n",
    "        for i in range(1, n + 1):\n",
    "            xorsum ^= i\n",
    "        # 找到最低有效位1，xorsum是消失数字的异或结果，代表这两个数在这一位不同\n",
    "        lsb = xorsum & (-xorsum)\n",
    "        num1 = num2 = 0\n",
    "        for num in nums:\n",
    "            if num & lsb:\n",
    "                num1 ^= num\n",
    "            else:\n",
    "                num2 ^= num\n",
    "        for i in range(1, n + 1):\n",
    "            if i & lsb:\n",
    "                num1 ^= i\n",
    "            else:\n",
    "                num2 ^= i\n",
    "        return [num1, num2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        xorsum = 0\n",
    "        n = len(nums) + 2\n",
    "        for num in nums:\n",
    "            xorsum ^= num\n",
    "        for i in range(1, n + 1):\n",
    "            xorsum ^= i\n",
    "        \n",
    "        lsb = xorsum & (-xorsum)\n",
    "        type1 = type2 = 0\n",
    "        for num in nums:\n",
    "            if num & lsb:\n",
    "                type1 ^= num\n",
    "            else:\n",
    "                type2 ^= num\n",
    "        for i in range(1, n + 1):\n",
    "            if i & lsb:\n",
    "                type1 ^= i\n",
    "            else:\n",
    "                type2 ^= i\n",
    "        \n",
    "        return [type1, type2]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        xorsum = 0\n",
    "        n = len(nums) + 2\n",
    "        for num in nums:\n",
    "            xorsum ^= num\n",
    "        for i in range(1, n + 1):\n",
    "            xorsum ^= i\n",
    "        \n",
    "        lsb = xorsum & (-xorsum)\n",
    "        type1 = type2 = 0\n",
    "        for num in nums:\n",
    "            if num & lsb:\n",
    "                type1 ^= num\n",
    "            else:\n",
    "                type2 ^= num\n",
    "        for i in range(1, n + 1):\n",
    "            if i & lsb:\n",
    "                type1 ^= i\n",
    "            else:\n",
    "                type2 ^= i\n",
    "        \n",
    "        return [type1, type2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        # math \n",
    "        n = len(nums)\n",
    "        N = n + 2\n",
    "        x_y_sum = N * (1 + N) // 2 - sum(nums) \n",
    "        pivot = x_y_sum // 2 # 因为x和y必然不相等，那两者不可能同时位于pivot的同一侧，因此从1到pivot的总和减去小于等于pivot的值的和就是第一个缺失的数\n",
    "        first = pivot * (1 + pivot) // 2 - sum([x for x in nums if x <= pivot])\n",
    "        return [first, x_y_sum - first] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        xorsum = 0\n",
    "        n = len(nums)+2\n",
    "        for num in nums:\n",
    "            xorsum ^= num\n",
    "        for i in range(1, n+1):\n",
    "            xorsum ^= i\n",
    "        lsb = xorsum &(-xorsum)\n",
    "        type1 = type2 = 0\n",
    "        for num in nums:\n",
    "            if num & lsb:\n",
    "                type1 ^= num\n",
    "            else: \n",
    "                type2 ^= num\n",
    "        for i in range(1, n+1):\n",
    "            if i & lsb:\n",
    "                type1 ^= i\n",
    "            else:\n",
    "                type2 ^= i\n",
    "        return [type1, type2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        xorsum = 0\n",
    "        n = len(nums) + 2\n",
    "        for num in nums:\n",
    "            xorsum ^= num\n",
    "        for i in range(1, n + 1):\n",
    "            xorsum ^= i\n",
    "        \n",
    "        lsb = xorsum & (-xorsum)\n",
    "        type1 = type2 = 0\n",
    "        for num in nums:\n",
    "            if num & lsb:\n",
    "                type1 ^= num\n",
    "            else:\n",
    "                type2 ^= num\n",
    "        for i in range(1, n + 1):\n",
    "            if i & lsb:\n",
    "                type1 ^= i\n",
    "            else:\n",
    "                type2 ^= i\n",
    "        \n",
    "        return [type1, type2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        result = []\n",
    "        if len(nums) != 1:\n",
    "            list1 = [i for i in range(1,len(nums)+3)]\n",
    "            nums = sorted(nums)\n",
    "            nums = nums + [0]*2\n",
    "            for i in range(len(list1)):\n",
    "                if list1[i] != nums[i]:\n",
    "                    nums.insert(i,0)\n",
    "                    result.append(i+1)\n",
    "            return result\n",
    "        else:\n",
    "            list1 = [1,2,3]\n",
    "            list1.remove(nums[0])\n",
    "            return list1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)+2\n",
    "        dic = {}\n",
    "        for i in nums:\n",
    "            if i not in dic:\n",
    "                dic[i]=1\n",
    "        a = []\n",
    "        for i in range(1,n+1):\n",
    "            if i not in dic:\n",
    "                a.append(i)\n",
    "        return a[0],a[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        ns=set(nums)\n",
    "        res=[]\n",
    "        j=0\n",
    "        for i in range(1,max(max(ns),1)+3):\n",
    "            if i not in ns:\n",
    "                res.append(i)\n",
    "                j+=1\n",
    "            if j==2:\n",
    "                return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def missingTwo(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        nums = set(nums)\n",
    "        for i in range(1, n+3):\n",
    "            if i not in nums:\n",
    "                res.append(i)\n",
    "        return res\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
